package com.mid;

import java.util.*;

/**
 * Created by Lxk on 2020/1/29.
 */
public class Solution216 {

    private int[] numArr = new int[9];

    private List<List<Integer>> res = new ArrayList<>();

    private Set<String> strSet = new HashSet<>();

    private Set<Integer> numSet = new HashSet<>();

    /**
     * 尝试使用1-9为基数，然后在每次处理时从其中选择一个
     *
     * @param pos
     * @param target
     * @param limit
     */
    private void findNumArr(int pos, int target, int limit) {
        if (target == 0 && pos == limit) {
            //find
            List<Integer> curList = new ArrayList<>();
            for (int i = 0; i < pos; i++) {
                curList.add(numArr[i]);
            }
            Collections.sort(curList);
            StringBuffer sb = new StringBuffer();
            for (Integer val : curList) {
                sb.append(val);
            }
            if (strSet.add(sb.toString())) {
                res.add(curList);
            }
            return;
        }
        for (int i = 1; i <= 9; i++) {
            if (i <= target && pos < 9 && pos < limit) {
                if (numSet.add(i)) {
                    numArr[pos] = i;
                    findNumArr(pos + 1, target - i, limit);
                    numSet.remove(i);
                }
            }
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        res.clear();
        findNumArr(0, n, k);
        return res;
    }

    /**
     * 转换维度，对于某个数值，选取或者不选取
     *
     * @param data
     * @param pos
     * @param target
     * @param limit
     */
    private void findNumArrNew(int data, int pos, int target, int limit) {
        if (pos > limit) {
            return;
        }
        if (target == 0 && pos == limit) {
            List<Integer> curList = new ArrayList<>();
            for (int i = 0; i < pos; i++) {
                curList.add(numArr[i]);
            }
            Collections.sort(curList);
            res.add(curList);
            return;
        } else if (data > 9) {
            return;
        }
        //不选取这个数字
        findNumArrNew(data + 1, pos, target, limit);
        //选取这个数字
        numArr[pos] = data;
        findNumArrNew(data + 1, pos + 1, target - data, limit);
    }

    public List<List<Integer>> combinationSum3New(int k, int n) {
        res.clear();
        findNumArrNew(1, 0, n, k);
        return res;
    }

    public static void main(String[] args) {
        Solution216 solution216 = new Solution216();
        System.out.println(solution216.combinationSum3New(9, 45));
    }

}
